import java.util.ArrayList;
import java.util.List;

/**
 * 找到字符串中所有字母异位词
 * 给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。
 * 不考虑答案输出的顺序。
 * 异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
 */

public class demo3 {
    public List<Integer> findAnagrams(String ss, String pp) {
        List<Integer> ret = new ArrayList<>();
        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();
        int[] hash1 = new int[26];
        for (char ch : p) hash1[ch - 'a']++;
        int[] hash2 = new int[26];
        int m = p.length;
        for (int left = 0, right = 0, count = 0; right < s.length; right++) {
            char in = s[right];
            //hash2[in-'a']++;
            if (++hash2[in-'a'] <= hash1[in-'a']) count++;
            if (right - left + 1 > m) {
                char out = s[left++];
                if (hash2[out - 'a']-- <= hash1[out - 'a']) count--;
                //left++;
            }
            if (count == m) {
                ret.add(left);
            }
        }
        return ret;
    }


}
